class Solution:
    """
    使用动态规划， 方程为dp[n] = dp[n-1] + dp[n-2]
    由方程可知，初始化dp时需要初始化前三位数，即dp[0], dp[1], dp[2] = 0, 1, 2
    """

    @staticmethod
    def climb_stairs(n: int) -> int:
        # 当n<2时，直接返回n即可
        if n <= 2:
            return n
        # 创建dp
        dp = [0 for j in range(n + 1)]
        # c初始化dp
        dp[0], dp[1], dp[2] = 0, 1, 2
        # 求dp[n]
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]


if __name__ == '__main__':
    print(Solution().climb_stairs(10))
